#include <iostream>
#include <stack>
#include <cmath>
#include <queue>

using namespace std;

class BinaryTreeNode
{
    public:
        char data;
        char flag; // l 表示从左过来，r表示从右子树过来
        //构造函数
        BinaryTreeNode(){
            leftchild = NULL;
            rightchild = NULL;
        };  

        BinaryTreeNode* leftchild;
        BinaryTreeNode* rightchild;
};


//定义二叉树模板
class BinaryTree
{
    private:
        BinaryTreeNode * head; //头指针

    public:
        BinaryTreeNode * root; //根结点
        //构造函数，默认空树
        BinaryTree(){
            root = NULL;
            head = root;
        };  

        /*
         * 构建二叉树
         * @param T   BinaryTreeNode *&  传入二叉树类型的地址
         * @param strPointer   char*  输入字符串首字母地址
         *
         */
        void create(BinaryTreeNode* &T, char* &strPointer){
            BinaryTreeNode* curPointer;
            BinaryTreeNode* TNode;
            if(*strPointer !=0){
                //如果遇到井号，构建空叶子节点
                if(*strPointer =='#'){
                    T = NULL;
                }else{
                     T = new BinaryTreeNode();
                     T->data = *strPointer;

                    //创建左子树
                    create(T->leftchild, ++strPointer); 

                    //创建右子树
                    create(T->rightchild, ++strPointer); 
                }
            }
        }

        //中序遍历二叉树
        int countLeaves(){
            stack <BinaryTreeNode*> aStack;
            BinaryTreeNode* pointer=root;
            int total = 0;

            pointer->flag ='l'; //做左子树标记
            //根结点入栈
            aStack.push(pointer);

            while(!aStack.empty()){
                //未标记右子树的，左子树需要走到尽头
                while(pointer->leftchild != NULL && (pointer->flag ==0||pointer->flag=='l')){ 
                    pointer->leftchild->flag = 'l';   //做左子树标记
                    aStack.push(pointer->leftchild);
                    pointer = pointer->leftchild;
                }

                if(!aStack.empty()){
                    pointer = aStack.top();

                   //弹出栈顶元素,继续下级的遍历
                    aStack.pop();

                    //如果该节点没有左右孩子，则为叶结点
                    if(pointer->leftchild == NULL && pointer->rightchild == NULL){
                        total++;
                    }

                   //右子树进栈
                    if(pointer->rightchild != NULL){
                        aStack.push(pointer->rightchild);
                        pointer = pointer->rightchild;
                    }else{
                        if(!aStack.empty()){
                            aStack.top()->flag = 'r'; //如果从右子树过来的，需要做右子树标记
                        }
                    }
                }
            }

            return total;
        }

        /*
         *  获取树的层次
         *
         */
        int getLevel(BinaryTreeNode *root)
        {
            if(root == NULL) return 0;
            return max(getLevel(root->leftchild), getLevel(root->rightchild))+1;
        }

        //广度遍历，并打印输出树
        void printTree()
        {
            

        }
        
        void treeprint(BinaryTreeNode* T,int level)  
        {  
           if (!T)             //如果指针为空，返回上一层  
           {  
                  return;  
               }  
            treeprint(T->rightchild,level+1);    //打印右子树，并将层次加1  
           for (int i=0;i<level;i++)    //按照递归的层次打印空格  
           {  
                  cout <<"    ";  
               }  
           cout <<T->data <<" \n";  //输出根结点  
            treeprint(T->leftchild,level+1);    //打印左子树，并将层次加1  
        }  
};
